Accelerating Polynomial Homotopy Continuation on a Graphics Processing Unit with Double Double and Quad Double Arithmetic

摘要

Numerical continuation methods track a solution path defined by a homotopy.The systems we consider are defined by polynomials in several variables withcomplex coefficients. For larger dimensions and degrees, the numericalconditioning worsens and hardware double precision becomes often insufficientto reach the end of the solution path. With double double and quad doublearithmetic, we can solve larger problems that we could not solve with hardwaredouble arithmetic, but at a higher computational cost. This cost overhead canbe compensated by acceleration on a Graphics Processing Unit (GPU). We describeour implementation and report on computational results on benchmark polynomialsystems.